package com.example.leetcode.tree;

/**
 * 找到两个节点的最近公共祖先
 */
public class Tree5 {
    public static void main(String[] args) {
    }

    // 核心思想：
    // 分析可知，对于节点 o1, o2 的最近公共祖先，只存在三种情况：
    // o1 ，o2 分别位于root的左右子树上
    // o1 = root, 且 o2 位于root的左子树/右子树中
    // o2 = root, 且 o1 位于root的左子树/右子树中


//    递归情况：
//            1.当到达空节点（既叶子节点的子节点）时，直接返回空
//2.当root等于 o1 或 o2 时，返回root
//3.若不为1， 2中情况，说明需要继续处理：
//    对左子树进行递归，返回值记为 t1
//    对右子树进行递归，返回值记位 t2
//    t1 ，t2 存在以下几种情况：
//            ①. 当t1, t2都为空时，说明root的左右子树中都不存在o1, o2， 返回空
//②. 当t1为空且t2不为空时，说明左子树找不到 o1, o2,所以返回 t2
//③. 当t2为空且t1不为空时，说明右子树找不到 o1, o2,所以返回 t1
//④. 当t1, t2都不为空时,说明o1, o2分别位于root的左右子树中，既root为答案，返回root
    public static int lowestCommonAncestor(TreeNode root, int o1, int o2) {
        if (root == null) {
            return -1;
        }

        // 当root等于 o1 或 o2 时，返回root
        if (root.val == o1 || root.val == o2) {
            return root.val;
        }


        int left = lowestCommonAncestor(root.left, o1, o2);
        int right = lowestCommonAncestor(root.right, o1, o2);

        // 左子树找不到o1,o2
        if (left == -1) {
            return right;
        }

        // 右子树找不到o1,o2
        if(right == -1) {
            return left;
        }

        return root.val;
    }
}
